/*
 * @lc app=leetcode.cn id=648 lang=cpp
 *
 * [648] 单词替换
 */

// @lc code=start

struct TireNode {
    TireNode *next[26];
    bool isEnd;
    string word;
    TireNode() {
        memset(next, 0, sizeof(next));
        isEnd = false;
        word = "";
    }
};

struct Tire {
    TireNode *root;
    Tire() { root = new TireNode(); }
    void insert(string word) {
        TireNode *p = root;
        for (auto c : word) {
            if (p->next[c - 'a'] == NULL) {
                p->next[c - 'a'] = new TireNode();
            }
            p = p->next[c - 'a'];
        }
        p->isEnd = true;
        p->word = word;
    }
    string search(string word) {
        TireNode *p = root;
        for (auto c : word) {
            if (p->next[c - 'a'] == NULL) {
                return "";
            }
            p = p->next[c - 'a'];
            if (p->isEnd) {
                return p->word;
            }
        }
        return "";
    }
};

class Solution {
public:
    string replaceWords(vector<string> &dictionary, string sentence) {
        Tire tire;
        for (auto word : dictionary) {
            tire.insert(word);
        }

        stringstream ss(sentence);
        string temp;
        vector<string> words;
        while (ss >> temp) {
            words.push_back(temp);
        }

        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            string replace = tire.search(word);
            if (replace != "") {
                words[i] = replace;
            }
        }

        return accumulate(words.begin(), words.end(), string{},
                          [](string a, string b) {
                              if (a == "") return b;
                              return a + " " + b;
                          });
    }
};
// @lc code=end
